package demo.practice.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class P94 {

    //https://leetcode-cn.com/problems/binary-tree-inorder-traversal/


    List<Integer> list= new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {

        if(root==null){
            return list;
        }

        if(root.left!=null){
            inorderTraversal(root.left);
        }


        list.add(root.val);

        if(root.right!=null){
            inorderTraversal(root.right);
        }

        return list;
    }

    public static void main(String[] args) {
        TreeNode r = new TreeNode(3);
        r.left = new TreeNode(5);
        r.left.left = new TreeNode(4);
        r.left.right = new TreeNode(8);
        r.right = new TreeNode(15);
        r.right.right = new TreeNode(20);
        r.right.left = new TreeNode(6);

        P94 p94 = new P94();
        List<Integer> list = p94.inorderTraversalStack(r);

    }

    //          3
    //        5   15
    //      4  8 6  20
    public List<Integer> inorderTraversalStack(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        //用栈实现
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        while (cur != null || !stack.isEmpty()){
            //内层循环将当前数据入栈
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            //出栈并将该元素放入到链表中
            top = stack.pop();
            list.add(top.val);
            //将cur指向栈顶元素的右孩子
            cur = top.right;
        }
        return list;
    }

}
